package structure;


import Tree.MyBinaryTree;

public class Test11 {
    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder();

    }
    //leetcode 110 平衡二叉树
    public static boolean isBalanced(MyBinaryTree.TreeNode root) {
        if(root == null) {
            return true;
        }else {
            return getLen(root) >= 0;
        }
    }
    public static int getLen(MyBinaryTree.TreeNode root){
        if(root == null){
            return 0;
        }
        int left = getLen(root.left);
        int right = getLen(root.right);
        if(Math.abs(left - right) > 1){
            return -1;
        }
        if(left < 0 || right < 0){
            return -1;
        }
        return Math.max(left,right) + 1;
    }
    //leetcode 106 从中序与后序遍历序列构造二叉树
    class Solution1 {
        public int start = 0;
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            start = postorder.length - 1;
            return buildTreechild(inorder,postorder,0,postorder.length - 1);
        }
        public TreeNode buildTreechild(int[] inorder,int[] postorder,int begin,int end){
            if(begin > end){
                return null;
            }
            int rootval = postorder[start];
            TreeNode root = new TreeNode(rootval);
            int index = findIndex(inorder,begin,end,rootval);
            start--;
            root.right = buildTreechild(inorder,postorder,index + 1,end);
            root.left = buildTreechild(inorder,postorder,begin,index - 1);
            return root;
        }
        public int findIndex(int[] inorder,int begin,int end,int rootval){
            for(int i = begin;i <= end;i++){
                if(inorder[i] == rootval){
                    return i;
                }
            }
            return -1;
        }
    }
    //leetcode 105 从前序与中序遍历序列构造二叉树
    class Solution0 {
        public int start = 0;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTreechild(preorder,inorder,0,inorder.length - 1);
        }
        public TreeNode buildTreechild(int[] preorder,int[] inorder,int begin,int end){
            if(begin > end){
                return null;
            }
            TreeNode root = new TreeNode(preorder[start]);
            int key = preorder[start];
            int index = findIndex(inorder,begin,end,key);
            start++;
            root.left = buildTreechild(preorder,inorder,begin,index - 1);
            root.right = buildTreechild(preorder,inorder,index + 1,end);
            return root;
        }
        public int findIndex(int[] inorder,int begin,int end,int key){
            for(int i = begin;i <= end;i++){
                if(inorder[i] == key){
                    return i;
                }
            }
            return -1;
        }
    }
}